#include<unordered_map>
#include<vector>
using namespace std;
class Solution {
private:
    vector<vector<unsigned long long>> initDP(int m, int n) {
        vector<vector<unsigned long long>> dp;
        for (int i = 0; i < m + 2; ++i) {
            dp.emplace_back(n + 2, i == 0 || i == m + 1 ? 1 : 0);
            dp.back().front() = 1;
            dp.back().back() = 1;
        }
        return dp;
    }

public:
    int findPaths(int m, int n, int N, int i, int j) {
        if (N == 0) return 0;
        int MOD = 1000000007;
        auto dp0 = initDP(m, n);
        auto dp1 = initDP(m, n);
        for (int k = 1; k < N; ++k) {
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    dp1[i][j] = (dp0[i - 1][j] + dp0[i + 1][j] + dp0[i][j - 1] + dp0[i][j + 1])% MOD;
                }
            }
            swap(dp0, dp1);
        }
        ++i;
        ++j;
        return (dp0[i - 1][j] + dp0[i + 1][j] + dp0[i][j - 1] + dp0[i][j + 1])% MOD;
    }
};
//
//int main() {
//    Solution sol;
//    sol.findPaths(2, 3, 8, 1, 0);
//}